#include<iostream>

/// @brief DoubleLinkedList的DT模板类 
/// @tparam DT DoubleLinkedList的类型
template <typename DT>
class DoubleLinkedList
{
private:
    /// @brief 节点Node
    struct Node
    {
        /// @brief data 数据;
        DT data;
        /// @brief prev 指针，指向上一个位置;
        Node *prev;
        /// @brief next 指针，指向下一个位置;
        Node *next;
        
        /// @brief Node构造函数，参数为左值DT，默认值为零元素，以及两个Node指针，默认参数为nullptr;
        /// @param d 赋值给data，数据;
        /// @param p 赋值给prev，指向上一个位置;
        /// @param n 赋值给next，指向下一个位置;
        Node( const DT & d = DT{ }, Node* p = nullptr, Node* n = nullptr)
        :data{ d }, prev{ p } , next{ n } { }

        /// @brief Node构造函数，参数为右值DT，以及两个Node指针，默认参数为nullptr;
        /// @param d 赋值给data，数据，std::move将左值强制转化为右值引用，通过右值引用，传值后d的空间将被释放，从而节省空间;
        /// @param p 赋值给prev，指向上一个位置;
        /// @param n 赋值给next，指向下一个位置;
        Node( DT && d, Node * p = nullptr, Node * n = nullptr )
        : data{ std::move( d ) }, prev{ p }, next{ n } { }
    };
public:

    /// @brief const_iterator类，用于存储一个指向当前节点的迭代器，同时通过运算符重载实现所需的迭代器运算;
    class const_iterator
    {
        public:

            /// @brief const_iterator 构造函数，使用初始化列表的方法，将current指针初始化为nullptr;
            const_iterator( ) : current{ nullptr }{ }

            /// @brief 重载*号（取值）;
            /// @return 返回当前const_iterator类中current指针的data值; 
            const DT & operator* ( ) const
            { return retrieve( ); }

            /// @brief 重载++号（前置递增）将原来const_iterator类中的current指针所指的位置指向下一个位置;
            /// @return 返回原来const_iterator类中的current指针的下一个位置的迭代器;
            const_iterator & operator++ ( )
            {
            current = current->next;
            return *this;
            }

            /// @brief 重载++号（后置递增）将原来const_iterator类中的current指针所指的位置指向下一个位置;
            /// @param int 参数只是用来区分不同的重载;
            /// @return 返回表示原来的const_iterator类中原来的current指针指向的位置的迭代器;
            const_iterator operator++ ( int )
            {
            const_iterator old = *this;
            ++( *this );//调用了上一个重载函数;
            return old;
            }

            /// @brief 重载--号（前置递减）将原来const_iterator类中的current指针所指的位置指向上一个位置;
            /// @return 返回原来const_iterator类中的current指针的上一个位置的迭代器;
            const_iterator & operator-- ( )
            {
            current = current->prev;
            return *this;
            }

            /// @brief 重载--号（后置递减）将原来const_iterator类中的current指针所指的位置指向上一个位置;
            /// @param int 参数只是用来区分不同的重载;
            /// @return 返回表示原来的const_iterator类中原来的current指针指向的位置的迭代器;
            const_iterator operator-- ( int )
            {
            const_iterator old = *this;
            --( *this );//调用了上一个重载函数;
            return old;
            }

            /// @brief 重载==号;
            /// @param rhs const_iterator 的引用;
            /// @return 当前const_iterator类中的current指针的位置是否与rhs.current是同一个位置，若相等返回true;
            bool operator== ( const const_iterator & rhs ) const
            { return current == rhs.current; }

            /// @brief 重载！=号;
            /// @param rhs const_iterator 的引用;
            /// @return 当前const_iterator类中的current指针的位置的迭代器与rhs是否不相等，若不相等返回true;
            bool operator!= ( const const_iterator & rhs ) const
            { return !( *this == rhs ); }//调用了上一个重载函数;

        protected:
            /// @brief Node指针current,用来指示当前位置;
            Node *current;
            
            /// @brief retrieve函数;
            /// @return 返回当前位置的data;
            DT & retrieve( ) const
            { return current->data; }

            /// @brief const_iterator 构造函数，使用初始化列表的方法，将current指针初始化为p;
            /// @param p 传入的Node指针p;
            const_iterator( Node *p ) : current{ p }{ }
 
            /// @brief 使得DoubleLinkedList<DT>可以与const_iterator类共享数据，const_iterator类中的函数均为DoubleLinkedList<DT>类中的友元函数;
            friend class DoubleLinkedList<DT>;
    };

    /// @brief 继承了const_iterator类，用于实现Node指针和const_iterator的转换
    class iterator: public const_iterator
    {
        public:
            /// @brief iterator 构造函数，使用初始化列表的方法，初始化为空;
            iterator( ) { }

            /// @brief 重载*号（取值），针对传入非const list的情况，调用了const_iterator类中的retrieve函数;
            /// @return 返回当前const_iterator类中current指针的data值;
            DT & operator* ( )
            { return const_iterator::retrieve( ); }
            
            /// @brief 重载*号（取值），针对传入const list的情况，调用了const_iterator类中的*重载函数;
            /// @return 返回当前const_iterator类中current指针的data值; 
            const DT & operator* ( ) const
            { return const_iterator::operator*( ); }

            /// @brief 重载++号（前置递增）将原来iterator类中的this指针所指的位置指向下一个位置;
            /// @return 返回表示原来iterator类中的current指针的下一个位置的迭代器;
            iterator & operator++ ( )
            {
                this->current = this->current->next;
                return *this;
            }
            
            /// @brief 重载++号（后置递增）将原来iterator类中的this指针所指的位置指向下一个位置;
            /// @param int 参数只是用来区分不同的重载;
            /// @return 返回表示原来的iterator类中原来的this指针指向的位置的迭代器;
            iterator operator++ ( int )
            {
                iterator old = *this;
                ++( *this );
                return old;
            }

            /// @brief 重载--号（前置递减）将原来iterator类中的this指针所指的位置指向上一个位置;
            /// @return 返回表示原来iterator类中的current指针的上一个位置的迭代器;
            iterator & operator-- ( )
            {
                this->current = this->current->prev;
                return *this;
            }

            /// @brief 重载--号（后置递减）将原来iterator类中的this指针所指的位置指向上一个位置;
            /// @param int 参数只是用来区分不同的重载;
            /// @return 返回表示原来的iterator类中原来的this指针指向的位置的迭代器;
            iterator operator-- ( int )
            {
                iterator old = *this;
                --( *this );
                return old;
            }
        
        protected:
            /// @brief iterator 构造函数，使用初始化列表的方法，将const_iterator类初始化为p;
            /// @param p 传入的Node指针p;
            iterator( Node *p ) : const_iterator{ p } { }

            /// @brief 使得DoubleLinkedList<DT>可以与const_iterator类共享数据，iterator类中的函数均为DoubleLinkedList<DT>类中的友元函数;
            friend class DoubleLinkedList<DT>;
    };

public:
    /// @brief 调用链表初始化函数以构造一个未传参数的DoubleLinkedList;
    DoubleLinkedList( )
    {
      init( );
    }

    /// @brief 首先调用链表初始化函数以构造一个未传参数的DoubleLinkedList，然后将传入的DoubleLinkedList对象通过push_back函数加在链表末尾;
    /// @param rhs 传入的DoubleLinkedList类对象;
    DoubleLinkedList( const DoubleLinkedList & rhs )
    {
        init( );
        for( auto & x : rhs )
        push_back( x );
    }
    

    /// @brief 析构函数，释放内存，防止内存泄漏;
    ~DoubleLinkedList( )
    {
        clear( );
        delete head;
        delete tail;
    }

    /// @brief 重载=号（赋值），参数是左值DoubleLinkedList，通过调用std::swap函数完成;
    /// @param rhs 传入的DoubleLinkedList类对象;
    /// @return 指针this指向的DoubleLinkedList对象;
    DoubleLinkedList & operator= ( const DoubleLinkedList & rhs )
    {
        DoubleLinkedList copy = rhs;
        std::swap( *this, copy );//swap函数交换地址;
        return *this;
    }
    

    /// @brief 以DoubleLinkedList右值为参数的DoubleLinkedList构造函数;
    /// @param rhs 传入的DoubleLinkedList右值对象;
    DoubleLinkedList( DoubleLinkedList && rhs )
        : theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
    {
        rhs.theSize = 0;
        rhs.head = nullptr;
        rhs.tail = nullptr;
    }
    
    /// @brief 重载=号（赋值），参数是右值DoubleLinkedList，通过调用std::swap函数完成;
    /// @param rhs 传入的DoubleLinkedList右值对象;
    /// @return 指针this指向的DoubleLinkedList对象;
    DoubleLinkedList & operator= ( DoubleLinkedList && rhs )
    {
        std::swap( theSize, rhs.theSize );
        std::swap( head, rhs.head );
        std::swap( tail, rhs.tail );
        return *this;
    }
    

    /// @brief begin函数，用于取得链表的开头;
    /// @return 返回代表head->next的iterator;
    iterator begin( )
    { return { head->next }; }

    /// @brief begin函数的重载，用于取得const链表的开头;
    /// @return 返回代表head->next的const_iterator;
    const_iterator begin( ) const
    { return { head->next }; }

    /// @brief end函数，用于取得链表的结尾;
    /// @return 返回代表tail的iterator;
    iterator end( )
    { return { tail }; }
    
    /// @brief end函数的重载，用于取得const链表的结尾;
    /// @return 返回代表tail的const_iterator;
    const_iterator end( ) const
    { return { tail }; }

    /// @brief size函数，用于取得链表的长度;
    /// @return 返回链表长度theSize;
    int size( ) const
    { return theSize; }
    
    /// @brief empty函数，用于判断链表是否被清空;
    /// @return 返回链表是否被清空，若是则返回true;
    bool empty( ) const
    { return size( ) == 0; }

    /// @brief clear函数，用于清空链表;
    void clear( )
    {
        while( !empty( ) )
        pop_front( );
    }
    
    /// @brief front函数，用于返回链表开头位置的data值;
    /// @return 返回一个DT类型的引用，即链表开头位置的data值;
    DT & front( )
    { return *begin( ); }

    /// @brief front函数的重载，用于返回链表开头位置的data值;
    /// @return 返回一个const DT类型的引用，即链表开头位置的data值;
    const DT & front( ) const
    { return *begin( ); }

    /// @brief back函数，用于返回end函数返回的迭代器所指向位置的前一位的data值;
    /// @return 返回一个DT类型的引用，即end函数返回的迭代器所指向位置的前一位的data值;
    DT & back( )
    { return *--end( ); }

    /// @brief back函数的重载，用于返回end函数返回的迭代器所指向位置的前一位的data值;
    /// @return 返回一个DT类型的引用，即end函数返回的迭代器所指向位置的前一位的data值;
    const DT & back( ) const
    { return *--end( ); }

    /// @brief push_front函数，用于在链表开头插入DT类型的数据x;
    /// @param x 添加的数据x;
    void push_front( const DT & x )  
    { insert( begin( ), x ); }
    
    /// @brief push_front函数的重载，用于在链表开头插入DT类型的右值数据x;
    /// @param x 添加的右值数据x;
    void push_front( DT && x )
    { insert( begin( ), std::move( x ) ); }

    /// @brief push_back函数，用于在链表结尾插入DT类型的数据x;
    /// @param x 添加的数据x;
    void push_back( const DT & x )
    { insert( end( ), x ); }
    
    /// @brief push_back函数的重载，用于在链表结尾插入DT类型的右值数据x;
    /// @param x 添加的右值数据x;
    void push_back( DT && x )
    { insert( end( ), std::move( x ) ); }

    /// @brief pop_front函数，用于除去链表的开头;
    void pop_front( )
    { erase( begin( ) ); }

    /// @brief pop_back函数，用于除去链表的结尾，同时防止segmentation fault;
    void pop_back( )
    { erase( --end( ) ); }

    /// @brief printList函数，用于在屏幕上打印当前链表的值;
    void printList( ) 
    {
        iterator p{head->next};
        while( p.current->next )
        {
            std::cout << *p << ' ' ;
            p++;
        }
        std::cout << std::endl;
    }

    /// @brief insert函数，用于在链表中插入新的节点;
    /// @param itr 传入的迭代器参数，用于确定插入的位置;
    /// @param x 插入的数据x;
    /// @return 返回插入完毕后的迭代器;
    iterator insert( iterator itr, const DT & x )
    {
        Node *p = itr.current;
        theSize++;
        return { p->prev = p->prev->next = new Node{ x, p->prev, p } };
    }

    /// @brief insert函数的重载，用于在链表中插入新的节点;
    /// @param itr 传入的迭代器参数，用于确定插入的位置;
    /// @param x 插入的右值数据x;
    /// @return 返回插入完毕后的迭代器;
    iterator insert( iterator itr, DT && x )
    {
        Node *p = itr.current;
        theSize++;
        return { p->prev = p->prev->next 
        = new Node{ std::move( x ), p->prev, p } };
    }

    /// @brief erase函数，用于抹除链表中(头尾外)存在的节点;
    /// @param itr 传入的迭代器参数，用于确定删除的位置;
    /// @return 返回删除完毕后的迭代器;
    iterator erase( iterator itr )
    {
        iterator q;
        if (canerase(itr))
        {    
            Node *p = itr.current;
            iterator retVal{ p->next };
            p->prev->next = p->next;
            p->next->prev = p->prev;
            p->prev = nullptr;
            p->next = nullptr;
            delete p;
            theSize--;
            return retVal;
        }
        else
		{
            std::cout << "Can't erase." << std::endl;
            return q;
        } 
    }

    /// @brief erase函数的重载，用于删除一段节点;
    /// @param from 传入的迭代器参数，确定删除开始的位置;
    /// @param to 传入的迭代器参数，确定删除结束的位置;
    /// @return 返回删除完毕后的迭代器;
    iterator erase( iterator from, iterator to )
	{
        iterator itr = from;
		iterator q;
		for( itr = from; itr != to && canerase(itr);)
		itr = erase( itr );
		if(itr == to)
			return to;
		else
		{
            std::cout <<"Can't erase." << std::endl;
			return q;
        }
    }

    /// @brief canerase函数用于判断是否可以对该迭代器进行erase操作;
    /// @param itr 传入的迭代器引用;
    /// @return bool型变量表示是否可以进行erase;
    bool canerase (iterator & itr)
	{
		if( itr.current && 
			itr.current->prev && 
			itr.current->next)
			return true;
		else
			return false;
	}

private:

    /// @brief thesize DoubleLinkedList的长度;
    int theSize;
    /// @brief head 指针，指向DoubleLinkedList的第一个有意义的位置;
    Node *head;
    /// @brief tail 指针，指向DoubleLinkedList的最后一个有意义的位置;
    Node *tail;

    /// @brief 初始化函数，用于初始化链表;
    void init( )
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }

};
